package org.raymond.iworks.study.basic.structure.tree.binarytree;

/**
 * 需求:
 * 数列:{7,3,10,12,5,1,9}
 * 高效的完成对数据的查询和添加
 * 解决方案:
 * 1. 使用数组
 * 1.1 数组未排序,优点:直接在数组尾添加,速度快.缺点:查找速度慢
 * 1.2 数组排序,优点:可以使用二分查找,查找速度快.缺点:为了保证数组有序,在添加
 * 新数据时,找到插入位置后,后面的数据需要整体移动,速度慢
 * 2 使用链式存储-链表
 * 不管链表是否有序,查找速度都慢,添加速度闭数组快,不需要数据整体移动
 * 3 使用二叉排序树
 *
 * 二叉排序树介绍
 * BST(Binary Sort(Search) Tree),对于二叉排序树的任何一个非叶子节点,要求左子
 * 节点的值闭当前节点的值小,右子节点的值比当前节点的值大.
 * 特别说明: 如果有相同的值,可以将该节点放在左子节点或右子节点
 * 比如 {7,3,10,12,5,1,9}
 *      7                    7
 *   3    10    插入2=>    3    10
 *  1 5  9  12          1  5  9  12
 *                       2
 *
 * 二叉排序树的创建和遍历
 * 一个数组创建成对应的二叉排序树,并使用中序遍历二叉排序树
 * 二叉排序树的删除
 * 1) 删除叶子节点(如:2,5,9,12)
 * 1.1 找到待删除的节点 targetNode
 * 1.2 找到targetNode的父节点 parent
 * 1.3 确定targetNode是parent的左子节点还是右子节点
 * 1.4 根据前面的情况来对应删除
 * 左子节点 parent.left=null
 * 右子节点 parent.right=null
 *
 * 2) 删除只有一颗子树的节点(如:1)
 * 2.1 找到待删除的节点 targetNode
 * 2.2 找到targetNode的父节点 parent
 * 2.3 确定targetNode的子节点是左子节点还是右子节点
 * 2.4 确定targetNode是parent的左子节点还是右子节点
 * 2.5 如果targetNode有左子节点
 * 2.5.1 如果targetNode是parent的左子节点
 * parent.left=targetNode.left
 * 2.5.2 如果targetNode是parent的右子节点
 * parent.right=targetNode.left
 * 2.6 如果targetNode有右子节点
 * 2.5.1 如果targetNode是parent的左子节点
 * parent.left=targetNode.right
 * 2.5.2 如果targetNode是parent的右子节点
 * parent.right=targetNode.right
 *
 * 3) 删除有两颗子树的节点(如:7,3,10)
 * 3.1 找到待删除的节点 targetNode
 * 3.2 找到targetNode的父节点 parent
 * 3.3 从targetNode的右子树找到最小的节点
 * 3.4 用一个临时变量,将最小节点的值保存 temp
 * 3.5 删除该最小节点
 * 3.6 targetNode.value=temp
 * 假设要删10,其父节点是7,其右子树的最小值是12,则删除12节点,将10替换为12
 *
 * 为啥选择目标节点右子树的最小值节点来替换目标节点?
 * 因为是有序树,目标节点右子树的节点值都比左子树的节点大.因此选择右子树中最小的
 * 一个值替换目标节点,并作为左子树的父节点,可以保证依然满足排序二叉树的要求
 *
 *
 */
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int arr[] = {7,3,10,12,5,1,9,2};
        BinarySortTree tree = new BinarySortTree();
        for(int i=0; i<arr.length; i++){
            tree.add(new Node(arr[i]));
        }
        tree.infixOrder();

        /*
        tree.delete(2);
        tree.delete(5);
        tree.delete(9);
        tree.delete(12);
        tree.delete(7);
        tree.delete(3);
        tree.delete(10);
        tree.delete(1);
         */
        tree.delete(7);
        tree.delete(3);
        tree.delete(10);
        tree.delete(12);
        tree.delete(5);
        tree.delete(1);
        tree.delete(9);
        tree.delete(2);
        System.out.println("删除叶子节点后,中序遍历");
        tree.infixOrder();
    }
}

class BinarySortTree{
    private Node root;

    public Node root(){
        return root;
    }
    public void add(Node node){
        if(root==null){
            root = node;
        }else{
            root.add(node);
        }
    }
    public void infixOrder(){
        if(root!=null){
            root.infixOrder();
        }else{
            System.out.println("二叉排序树为空,不能遍历");
        }
    }

    public Node search(int value){
        if(root==null) return null;
        return root.search(value);
    }
    public Node searchParent(int value){
        if(root==null) return null;
        return root.searchParent(value);
    }
    public void delete(int value){
        if(root==null) return;
        // 如果要删除的是root,且
        if(root.value==value){
            // 如果树中只有这一个节点,则直接置空
            if(root.left==null && root.right==null) {
                root = null;
                return;
            // 如果树中左子树不为空,右子树为空,则上提左子树
            }else if(root.left!=null){
                root = root.left;
                return;
            // 如果树中右子树不为空,左子树为空,则上提右子树
            }else{
                root = root.right;
                return;
            }
        }
        Node targetNode = search(value);
        if(targetNode==null) return;
        Node parent = searchParent(value);
        // 不需要检查parent是否为空,因为此时的parent必然不为空
        // 如果要删除的节点是叶子节点
        if(targetNode.left==null && targetNode.right==null){
            // 要删除的是父节点的左子节点,注意value==targetNode.value
            if(parent.left!=null && parent.left.value==value){
                parent.left = null;
            }
            // 要删除的是父节点的右子节点
            if(parent.right!=null && parent.right.value==value){
                parent.right= null;
            }
        }
        // 删除有两颗树的非叶子节点
        // 需要从子树中找到一个节点代替被删除节点的位置,需要满足二叉排序树的要求
        // 即替代节点的值要大于左子树,小于右子树
        // 即可以选择左子树的最大节点或者右子树的最小节点
        else if(targetNode.left!=null && targetNode.right!=null){
            // 删除targetNode的右子树最小节点
            int rightMinVal = delRightTreeMin(targetNode.right);
            // 将最小节点的值赋给当前待删除节点,完成替代
            targetNode.value = rightMinVal;
        }
        // 删除只有一颗树的非叶子节点
        // 如果有左子节点
        else if(targetNode.left!=null){
            // 要删除的是父节点的左子节点,注意value==targetNode.value
            if(parent.left!=null && parent.left.value==value){
                parent.left = targetNode.left;
            }
            // 要删除的是父节点的右子节点
            if(parent.right!=null && parent.right.value==value){
                parent.right= targetNode.left;
            }
        }
        // 如果有右子节点
        else if(targetNode.right!=null){
            // 要删除的是父节点的左子节点,注意value==targetNode.value
            if(parent.left!=null && parent.left.value==value){
                parent.left = targetNode.right;
            }
            // 要删除的是父节点的右子节点
            if(parent.right!=null && parent.right.value==value){
                parent.right= targetNode.right;
            }
        }
    }

    /**
     *
     * @param node 二叉排序树的root
     * @return 返回以node为根节点的二叉排序树的最小值的节点的值
     */
    public int delRightTreeMin(Node node){
        Node target = node;
        // 循环查找左节点,找到最小值
        while(target.left!=null){
            target = target.left;
        }
        // target指向最左端节点,即最小值
        delete(target.value);
        return target.value;
    }
}

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    /**
     *
     * @param value 待查找的节点的值
     * @return
     */
    public Node search(int value){
        if(value==this.value){
            return this;
        }else if(value<this.value){
            if(left==null) return null;
            return left.search(value);
        }else{
            if(right==null) return null;
            return right.search(value);
        }
    }

    public Node searchParent(int value){
        if((left!=null && left.value==value)
                || (right!=null && right.value==value)){
            return this;
        }
        if(left!=null && value<this.value){
            return left.searchParent(value);
        }else if(right!=null && value>=this.value){
            return right.searchParent(value);
        }
        return null;
    }
    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    // 以递归的方式添加节点,并满足二叉排序树的要求
    public void add(Node node){
        if(node==null) return;

        // 如果插入的新节点的值小于当前节点,则新节点向左放置
        if(node.value<=this.value){
            if(this.left==null){
                this.left=node;
            }else{
                this.left.add(node);
            }
        }else{
            if(this.right==null){
                this.right=node;
            }else{
                this.right.add(node);
            }
        }
    }

    public void infixOrder(){
        if(this.left!=null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.infixOrder();
        }
    }
}
